package arithmetic;

import utils.PrintUtil;

/**
 * @Author: Jie
 * @Date: 2019/3/15 10:45
 * @Function :
 *
 * 63. 不同路径 II有石头障碍
 * https://blog.csdn.net/CarryNet/article/details/87860730 动态规划 2 题
 * 矩形方阵：有石头，左上->右下，路径数量。
 * 找到 起点到终点的路径数量。
 *
 * 思路：起始点的解 = 下面空格解 + 右边空格的解；（存在最优子结构  可以 递归）
 * 从左上角，到，右下角的步骤。
 *
 */
public class A_25_DynamicProgramming {

    private static int ston;

    public static void main(String[] args) {
        //8行 8列
        int [][] field = new int[8][8];//第一个8表示某行，即y坐标
//      start[7][0];
//      end[0][7];
        //标注石头位置
        ston = -1;
        field[1][1] = ston;
        field[1][5] = ston;
        field[2][3] = ston;
        field[2][4] = ston;
        field[2][6] = ston;
        field[3][2] = ston;
        field[4][0] = ston;
        field[4][2] = ston;
        field[4][5] = ston;
        field[5][4] = ston;
        field[6][2] = ston;
        field[6][6] = ston;

        int [][] fieldCount = new int[8][8];//第一个8表示某行，即y坐标
        //初始值
        fieldCount[0][7]=0;
        fieldCount[0][6]=1;
        fieldCount[1][7]=1;
        //从终点开始到出发点结束
        for (int i = 0; i < 8; i++) {//行
            for (int j = 7; j >=0 ; j--) { //列
//                start
                if( field[i][j] == ston ){
                    fieldCount[i][j] = 0;
                }else {
                    if (i==0 && j==7){//结束位置
                    }else if (i==0 && j==6){//结束位置，左边值，已经初始化
                    } else if (i==1 && j==7){//结束位置，上边值，已经初始化
                    }else {
                        fieldCount[i][j] = ((i-1)< 0 ? 0 :fieldCount[i-1][j]) + ((j+1) > 7 ? 0 : fieldCount[i][j+1]);
                    }
                }
            }
        }
        System.out.println("start");
        mPrint(fieldCount);
//        PrintUtil.printArraysInteger(fieldCount);
        System.out.println(fieldCount[7][0]);
    }

    private static void mPrint(int[][] fieldCount) {
        for (int i = fieldCount.length-1; i >=0; i--) {
            for (int j = 0; j < fieldCount[i].length; j++) {
                if (j==fieldCount[i].length-1){
                    System.out.println(fieldCount[i][j]);
                }else {
                    System.out.print(fieldCount[i][j]+" ");
                }
            }
        }
    }

}
